/*
 * SPDX-License-Identifier: BSD-3-Clause
 * Copyright (c) Huawei Technologies Co., Ltd. 2021-2023. All rights reserved.
 * Description: udk fbarray source file
 * Author: -
 * Create: 2021.4.19
 */
#include <stdbool.h>
#include <unistd.h>
#include <limits.h>

#include "securec.h"

#include "udk_common.h"
#include "udk_log.h"
#include "udk_fbarray.h"

#define MASK_SHIFT 6ULL
#define MASK_ALIGN (1ULL << MASK_SHIFT)
#define MASK_LEN_TO_IDX(x) ((x) >> MASK_SHIFT)
#define MASK_LEN_TO_MOD(x) ((x) - UDK_ALIGN_FLOOR((x), MASK_ALIGN))
#define MASK_GET_IDX(idx, mod) (((idx) << MASK_SHIFT) + (mod))

struct udk_used_mask {
    uint32_t n_masks;
    uint64_t data[1];
};

static struct udk_used_mask *udk_get_used_mask(void *data, uint32_t elt_sz, uint32_t len)
{
    return (struct udk_used_mask *)UDK_PTR_ADD(data, elt_sz * len);
}

static int udk_set_used(struct udk_fbarray *arr, uint32_t idx, bool used)
{
    struct udk_used_mask *mask = NULL;
    uint32_t mod = MASK_LEN_TO_MOD(idx);
    uint64_t mask_bit = 1ULL << mod;
    unsigned int msk_idx = MASK_LEN_TO_IDX(idx);
    bool already_used = false;

    if ((arr == NULL) || (idx >= arr->len)) {
        return -1;
    }
    mask = udk_get_used_mask(arr->data, arr->elt_sz, arr->len);

    /* prevent array from changing under us */
    udk_rwlock_write_lock(&arr->rwlock);

    already_used = (mask->data[msk_idx] & mask_bit) != 0;

    /* nothing to be done */
    if (used == already_used) {
        goto out;
    }

    if (used) {
        mask->data[msk_idx] |= mask_bit;
        arr->count++;
    } else {
        mask->data[msk_idx] &= ~mask_bit;
        arr->count--;
    }
out:
    udk_rwlock_write_unlock(&arr->rwlock);

    return 0;
}

static int udk_find_next(const struct udk_fbarray *arr, uint32_t start, bool used)
{
    const struct udk_used_mask *mask = udk_get_used_mask(arr->data, arr->elt_sz, arr->len);
    uint32_t idx, first_idx, first_mod, last_idx, last_mod;
    uint64_t last_mask, ignore_mask;

    first_idx = MASK_LEN_TO_IDX(start);
    first_mod = MASK_LEN_TO_MOD(start);
    ignore_mask = ~((1ULL << first_mod) - 1ULL);

    /* calculate ignore mask that array length may not be aligned */
    last_idx = MASK_LEN_TO_IDX(arr->len);
    last_mod = MASK_LEN_TO_MOD(arr->len);
    last_mask = ~(-(1ULL) << last_mod);

    for (idx = first_idx; idx < mask->n_masks; idx++) {
        uint64_t cur = mask->data[idx];
        int found;

        /* invert mask for free-entry search */
        if (!used) {
            cur = ~cur;
        }

        if (idx == last_idx) {
            cur &= last_mask;
        }

        /* ignore everything before start on first iteration */
        if (idx == first_idx) {
            cur &= ignore_mask;
        }

        /* check if we have any entries */
        if (cur == 0) {
            continue;
        }

        /* find first set bit */
        found = __builtin_ctzll(cur);
        return (int)MASK_GET_IDX(idx, (uint32_t)found);
    }

    /* find nothing */
    return -1;
}

static int udk_fbarray_find(struct udk_fbarray *array, uint32_t start, bool used)
{
    int ret = -1;

    if ((array == NULL) || (start >= array->len)) {
        return -1;
    }

    /* prevent array from changing under us */
    udk_rwlock_read_lock(&array->rwlock);

    if (!used) {
        if (array->len == array->count) { /* full for no free */
            goto out;
        }

        if (array->count == 0) { /* empty for free */
            ret = (int)start;
            goto out;
        }
    } else {
        if (array->count == 0) { /* empty for no used */
            goto out;
        }

        if (array->len == array->count) { /* full for used */
            ret = (int)start;
            goto out;
        }
    }

    ret = udk_find_next(array, start, used);

out:
    udk_rwlock_read_unlock(&array->rwlock);
    return ret;
}

static size_t udk_calc_mask_size(uint32_t len)
{
    /* mask must be multiple of MASK_ALIGN, even though length of array itself may not be aligned on that boundary */
    len = UDK_ALIGN_CEIL(len, MASK_ALIGN);
    return sizeof(struct udk_used_mask) + sizeof(uint64_t) * MASK_LEN_TO_IDX(len);
}

static size_t udk_calc_data_size(size_t page_sz, uint32_t elt_sz, uint32_t len)
{
    size_t data_sz = elt_sz * len;
    size_t msk_sz = udk_calc_mask_size(len);
    return UDK_ALIGN_CEIL(data_sz + msk_sz, page_sz);
}

static int udk_fully_validate(const char *name, uint32_t elt_sz, uint32_t len)
{
    if (name == NULL || elt_sz == 0 || len == 0 || len > INT_MAX) {
        return -1;
    }

    if (strnlen(name, UDK_FBARRAY_NAME_LEN) == UDK_FBARRAY_NAME_LEN) {
        return -1;
    }
    return 0;
}

int udk_fbarray_init(struct udk_fbarray *arr, const char *name, uint32_t len, uint32_t elt_sz)
{
    size_t page_sz, mmap_len;
    struct udk_used_mask *msk = NULL;
    void *data = NULL;

    if (arr == NULL) {
        return -1;
    }

    if (udk_fully_validate(name, elt_sz, len) != 0) {
        return -1;
    }

    page_sz = (size_t)sysconf(_SC_PAGESIZE);
    if (page_sz == (size_t)-1) {
        return -1;
    }

    /* calculate our memory limits */
    mmap_len = udk_calc_data_size(page_sz, elt_sz, len);
    data = calloc(1, mmap_len);
    if (data == NULL) {
        return -1;
    }

    /* populate data structure */
    if (strcpy_s(arr->name, sizeof(arr->name), name) != 0) {
        UDK_LOG(WARNING, COMMON, "copy arr name fail: %s\n", arr->name);
        free(data);
        return -1;
    }

    arr->data = data;
    arr->len = len;
    arr->elt_sz = elt_sz;
    arr->count = 0;

    msk = udk_get_used_mask(data, elt_sz, len);
    msk->n_masks = (uint32_t)MASK_LEN_TO_IDX(UDK_ALIGN_CEIL(len, MASK_ALIGN));

    udk_rwlock_init(&arr->rwlock);

    return 0;
}

int udk_fbarray_attach(struct udk_fbarray *arr)
{
    if (arr == NULL) {
        return -1;
    }

    UDK_LOG(WARNING, COMMON, "Not support fbarray attach for %s\n", arr->name);
    return -1;
}

int udk_fbarray_destroy(struct udk_fbarray *arr)
{
    if (arr == NULL) {
        return -1;
    }

    free(arr->data);
    (void)memset_s(arr, sizeof(*arr), 0, sizeof(*arr));
    return 0;
}

void *udk_fbarray_get(const struct udk_fbarray *arr, uint32_t idx)
{
    void *ret = NULL;

    if (arr == NULL) {
        return NULL;
    }

    if (idx >= arr->len) {
        return NULL;
    }

    ret = UDK_PTR_ADD(arr->data, idx * arr->elt_sz);

    return ret;
}

int udk_fbarray_find_idx(const struct udk_fbarray *arr, const void *elt)
{
    int ret = -1;
    void *end = NULL;

    if ((arr == NULL) || (elt == NULL)) {
        return -1;
    }

    end = UDK_PTR_ADD(arr->data, arr->elt_sz * arr->len);
    if ((elt < arr->data) || (elt >= end)) {
        return -1;
    }

    ret = (int)(UDK_PTR_DIFF(elt, arr->data) / arr->elt_sz);

    return ret;
}

int udk_fbarray_set_used(struct udk_fbarray *arr, uint32_t idx)
{
    return udk_set_used(arr, idx, true);
}

int udk_fbarray_set_free(struct udk_fbarray *arr, uint32_t idx)
{
    return udk_set_used(arr, idx, false);
}

int udk_fbarray_find_next_free(struct udk_fbarray *arr, uint32_t start)
{
    return udk_fbarray_find(arr, start, false);
}

int udk_fbarray_find_next_used(struct udk_fbarray *arr, uint32_t start)
{
    return udk_fbarray_find(arr, start, true);
}
